# 这里是快速排序 ——它就像给一群学生按身高排队，而且用的是“分而治之”的聪明办法。

# 算法思想: 分治法 分而治之
# 核心思想：“挑一个人，小的靠左，大的靠右”

# 时间复杂度: O(nlogn)
# 空间复杂度: O(logn)

# 1. 选个“标杆”（Pivot）：比如随便挑一个学生作为身高参考。 pivot: 基准值  选基准值，有多种选法，比如选第一个元素，选最后一个元素，选随机一个元素/中间值
# 2. 分组：让比标杆矮的站左边，比标杆高的站右边。
# 3. 递归处理：对左边和右边的两组人重复同样的操作，直到每组只剩1人（自然就有序了）。


# 1. 选个基准值
# 2. 以基准值为参照，将数组分为两部分
# 3. 递归处理：对左边和右边的两组人重复同样的操作，直到每组只剩1人（自然就有序了）。

def quick_sort(arr):
    length = len(arr)
    if length <= 1:
        return arr
    pivot = arr[0]
    left = []
    right = []
    for i in range(1, length):
        if arr[i] < pivot:
            left.append(arr[i])
        else:
            right.append(arr[i])
    return quick_sort(left) + [pivot] + quick_sort(right)



### 易懂版代码实现，实际优化版会原地排序
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[-1]  # 选最后一个当标杆
    left = [x for x in arr[:-1] if x <= pivot]
    right = [x for x in arr[:-1] if x > pivot]
    return quick_sort(left) + [pivot] + quick_sort(right)

print(quick_sort([5, 2, 9, 1, 7]))  # 输出 [1, 2, 5, 7, 9]

# 这种写法后面再学
# def quick_sort(arr, low, high):
#     if low >= high:
#         return












































# 1. 选基准值 ： 一般选第一个元素
# 2. 分区： 从左到右遍历，找到第一个比基准值大的元素，记录下它的索引。
# 3. 交换： 交换基准值和这个比基准值大的元素的位置。
# 4. 分区： 从右到左遍历，找到第一个比基准值小的元素，记录下它的索引。
# 5. 交换： 交换基准值和这个比基准值小的元素的位置。
# 6. 重复： 重复步骤2-5，直到左指针和右指针相遇。
# 7. 交换： 交换基准值和左指针的位置。
# 8. 返回： 返回基准值的索引。

# 3. 递归处理： 对基准值左边的子数组和右边的子数组分别递归调用快速排序。

# 4. 结束： 当子数组的长度为1时，排序完成。
# def partition(arr, low, high):
#     pivot = arr[low]
#     while low < high:
#         while low < high and arr[high] >= pivot:
#             high -= 1
#         arr[low] = arr[high]
#         while low < high and arr[low] <= pivot:
#             low += 1
#         arr[high] = arr[low]
#     arr[low] = pivot
#     return low
